#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
struct elem
{
    int val, cnt;
    elem(int val = 0, int cnt = 1) : val(val), cnt(cnt){};
    bool operator<(const elem &e) const { return this->cnt > e.cnt; }
};
void sortK(vector<elem> &arr, int l, int r, int k)
{
    if (l >= r)
        return;
    swap(arr[r], arr[(l + r) / 2]);
    elem pivot = arr[r];
    int i = l - 1;
    for (int j = l; j < r; ++j)
    {
        if (arr[j] < pivot)
            swap(arr[++i], arr[j]);
    }
    swap(arr[i + 1], arr[r]);
    if (i + 1 == k)
        return;
    if (i + 1 > k)
        sortK(arr, l, i, k);
    else
        sortK(arr, i + 2, r, k);
}
class Solution
{
public:
    vector<elem> arr;
    vector<int> ans;
    vector<int> topKFrequent(vector<int> &nums, int k)
    {
        map<int, int> count;
        for (auto &it : nums)
        {
            count[it]++;
        }
        for (auto &it : count)
        {
            arr.push_back(elem(it.first, it.second));
        }
        sortK(arr, 0, arr.size() - 1, k);
        for (int i = 0; i < k; ++i)
        {
            ans.push_back(arr[i].val);
        }
        return ans;
    }
};
int main()
{
    int k = 2;
    vector<int> nums = {5, 2, 5, 3, 5, 3, 1, 1, 3};
    Solution slover;
    vector<int> ans = slover.topKFrequent(nums, k);
    for (auto &it : ans)
    {
        printf(" %d", it);
    }
    return 0;
}